package huawei.window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/repeated-dna-sequences/
 * 最有性能那个,列举了所有测试样例答案,就离谱!!!
 */
public class J187 {
    public static void main(String[] args) {
        System.out.println(findRepeatedDnaSequences2("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
    }
    public static List<String> findRepeatedDnaSequences(String s) {
        /**
         * 基础方案,hash表
         */
        HashMap<String,Integer> map=new HashMap<>();
        List<String> data =new ArrayList<>();
        for (int i = 0; i+10 <= s.length(); i++) {
            String tmp = s.substring(i,i+10);
            int count =map.getOrDefault(tmp,0);
            if(count==0){
                map.put(tmp,1);
            }else if(count==1){
                map.put(tmp,2);
                data.add(tmp);
            }
        }
        return data;
    }

    public static List<String> findRepeatedDnaSequences2(String s) {
        /**
         * dna序列只有四个字母,可以用两个bit位表示,
         * 长度10 即用20位表示,即子串可以用int来表示
         * 本质,通过int比较相同,性能比string更好,
         * 实际测试,并没有性能上的提升.
         */
        int cur = 0;
        List<String> data =new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            cur= cur<<2|bit(s.charAt(i));
            if (i+1>=10){
                int count = map.getOrDefault(cur,0);
                if(count==0){
                    map.put(cur,1);
                }else if(count==1){
                    map.put(cur,2);
                    data.add(s.substring(i-9,i+1));
                }
                cur = cur^(bit((s.charAt(i-9)))<<18);
            }
        }
        return data;
    }
    private static int bit(char c){
        if(c=='A'){
            return 0b00;
        }
        if(c=='C'){
            return 0b01;
        }
        if(c=='G'){
            return 0b10;
        }
        return 0b11;
    }
}
